package sort;

import java.util.Arrays;

/**
 * 插入排序
 */
public class InsertSort {
    public static void main(String[] args) {

        int[] arry = new int[10000];
        for (int i = 0; i <10000 ; i++) {
            arry[i] = (int)(Math.random()*80000);
        }
        insertSort(arry);

    }

    //插入排序
    public static void insertSort(int[] arr){
        for (int i = 1; i <arr.length ; i++) {
            int insertVal = arr[i];  //数组的第二个数据
            int insertIndex = i-1;  //第二个数据的前一个索引

            while (insertIndex>=0 && insertVal<arr[insertIndex]){
                arr[insertIndex+1] = arr[insertIndex]; //把前面那个数后移
                insertIndex--;
            }

            if(insertIndex +1 != i){//前一个
                arr[insertIndex +1] = insertVal;
            }

        }
        System.out.println(Arrays.toString(arr));
    }
}
